﻿#include "bpt_leaf.h"


bool BPTLeaf::spilled() {
	return size > capacity;
}

BPTLeaf* BPTLeaf::split(unsigned long& ret_min_key) {
	/*
	* ret_min_key: 分裂返回右节点的最小值，作为父节点的key
	*/
	assert(spilled());
	// 溢出则分裂
	BPTLeaf* new_leaf = new BPTLeaf(capacity);
	// 拷贝
	size /= 2;
	new_leaf->size = capacity - size + 1;
	for (int i = size; i <= capacity; i++) {
		new_leaf->keys[i - size] = keys[i];
		new_leaf->vals[i - size] = vals[i];
	}

	ret_min_key = new_leaf->keys[0];
	return new_leaf;
}

void BPTLeaf::print() {
	printf("Leaf-s%d:", size);
	for (int i = 0; i < size - 1; i++) {
		printf("%ld|", keys[i]);
	}
	printf("%ld", keys[size - 1]);
}

BPTLeaf::BPTLeaf(int cap) :
	capacity(cap)
{
	// 多分配一个，同理
	keys = new unsigned long[cap + 1];
	vals = new unsigned long[cap + 1];
}

BPTLeaf::~BPTLeaf() {
	delete [] keys;
	delete [] vals;
}

bool BPTLeaf::is_leaf() {
	return true;
}

void BPTLeaf::__insert(int loc, unsigned long key, unsigned long val) {
	// 直接插入
	for (int i = size - 1; i >= loc; i--) {
		keys[i + 1] = keys[i];
		vals[i + 1] = vals[i];
	}
	keys[loc] = key;
	vals[loc] = val;

	size++;
}

bool BPTLeaf::insert(unsigned long key, unsigned long val) {
	/* 返回值表示是否插入的重复元，不允许插入重复元 */
	int loc;
	if (bn_search(keys, key, size, loc)) {
		// 重复元
		return false;
	}

	// 直接插入
	__insert(loc, key, val);

	return true;
}


bool BPTLeaf::remove(unsigned long key) {
	int loc;
	if (bn_search(keys, key, size, loc)) {
		__remove(loc);
		return true;
	}
	return false;
}

void BPTLeaf::__remove(int loc) {
	for (int i = loc + 1; i < size; i++) {
		keys[i - 1] = keys[i];
		vals[i - 1] = vals[i];
	}
	size--;
	assert(size >= 0);
}

bool BPTLeaf::concealed() {
	return concealed(size);
}

bool BPTLeaf::concealed(int c) {
	// 因为分裂时最小的一边就是(capacity + 1) / 2
	return c < (capacity + 1) / 2;
}

unsigned long BPTLeaf::borrow(BPTNode* silbing, unsigned long key, bool l_r) {
	/*
	* key	: leaf中不使用
	* l_r	: silbing是左兄弟还是右兄弟
	* return: 用于父节点更新的key
	*/
	BPTLeaf* s_node = (BPTLeaf*)silbing;
	// 向左兄弟节点借一个
	// 将左兄弟的尾元移动到当前节点的首部
	if (l_r) {
		__insert(0, s_node->keys[s_node->size - 1], s_node->vals[s_node->size - 1]);
		//s_node->size--;
		s_node->__remove(s_node->size - 1);
		return keys[0];
	}

	// 向右兄弟节点借
	// 将右兄弟的首元移动到当前的尾部
	__insert(size, s_node->keys[0], s_node->vals[0]);
	s_node->__remove(0);
	return s_node->keys[0];
}

void BPTLeaf::append(BPTNode* node, unsigned long key) {
	/*将node的所有值追加到当前节点之后
	* node中所有值必须大于当前节点
	* key: leaf中不使用
	*/
	BPTLeaf* l_node = (BPTLeaf*)node;
	assert(l_node->size + size <= capacity);
	assert(l_node->keys[0] > keys[0]);
	
	for (int i = 0; i < l_node->size; i++) {
		keys[size + i] = l_node->keys[i];
		vals[size + i] = l_node->vals[i];
	}

	size += l_node->size;
}

bool BPTLeaf::contain(unsigned long key) {
	int loc;
	return bn_search(keys, key, size, loc);
}


char* BPTLeaf::serialize(int& len) {
	/*序列化格式说明-按字节顺序
	* sizeof(int)			: 序列化长度
	* 1						: 标志字节
	* sizeof(int)			: size字段
	* sizeof(ulong)*size	: keys数组
	* sizeof(ulong)*size	: vals数组
	* sizeof(int)			: capacity字段
	*
	* sibling字段不记录，构造树时自动连接
	*/
	len = sizeof(int) * 3 + 1 + sizeof(unsigned long) * size * 2;
	char flags = BPT_LEAF;

	char* serialization = new char[len];
	char* org_serialization = serialization;
	((int*)serialization)[0] = len;
	serialization += sizeof(int);
	serialization[0] = flags;
	serialization += 1;
	((int*)serialization)[0] = size;
	serialization += sizeof(int);
	for (int i = 0; i < size; i++) {
		((unsigned long*)serialization)[i] = keys[i];
	}
	serialization += sizeof(unsigned long) * size;

	for (int i = 0; i < size; i++) {
		((unsigned long*)serialization)[i] = vals[i];
	}
	serialization += sizeof(unsigned long) * size;
	((int*)serialization)[0] = capacity;

	return org_serialization;
}

bool BPTLeaf::load(char* serialization) {
	/*
	* 注意并没有完全检查节点序列的完整性
	* 节点数据被破坏仍有可能被序列化
	* 但最终的BPT将不正确
	*/
	int len = ((int*)serialization)[0];
	if (len < 0) return false;
	serialization += sizeof(int);
	char flags = serialization[0];
	if (!(flags & BPT_LEAF)) return false;
	serialization += 1;

	size = ((int*)serialization)[0];
	serialization += sizeof(int);
	for (int i = 0; i < size; i++) {
		keys[i] = ((unsigned long*)serialization)[i];
	}
	serialization += sizeof(unsigned long) * size;

	for (int i = 0; i < size; i++) {
		vals[i] = ((unsigned long*)serialization)[i];
	}
	serialization += sizeof(unsigned long) * size;
	capacity = ((int*)serialization)[0];
	if (capacity < 0) return false;

	return true;
}
